/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0) return null;
        if(lists.length==1)return lists[0];
        int length = lists.length%2==0?lists.length/2:lists.length/2+1;
        ListNode[] ls1 = new ListNode[length];
        ListNode[] ls2 = new ListNode[lists.length-length];
        for(int i=0; i<lists.length; i++){
            if(i<length){
                ls1[i] = lists[i];
            }else{
                ls2[lists.length-1-i] = lists[i];
            }
        }
        ListNode node1 = mergeKLists(ls1);
        ListNode node2 = mergeKLists(ls2);
        return mergeList(node1,node2);
    }

    private ListNode mergeList(ListNode node1, ListNode node2){
        ListNode node = new ListNode();
        ListNode tmp = node;
        while(node1!=null&&node2!=null){
            if(node1.val<node2.val){
                tmp.next = node1;
                node1 = node1.next;
            }else{
                tmp.next = node2;
                node2 = node2.next;
            }
            tmp = tmp.next;
        }
        if(node1==null)tmp.next=node2;
        if(node2==null)tmp.next=node1;
        return node.next;
    }
}